﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//对选择排序进行优化：单次循环找出数组的最大值以及最小值，
//并且将通过比较数组元素，赋值最值改为了直接将下标赋值，
//不需要后续再通过值来找下标了，上述优化大大提升了原始版本的性能（时间复杂度）
//以下以顺序排序作为示例

void swap(int* pa, int* pb)
{
	int c = *pa;
	*pa = *pb;
	*pb = c;
}
//选择排序
void ​​SelectionSort(int* arr, int sz)
{
	int i = 0, j = 0;
	int start = 0, end = sz - 1;//设置开始和结束的范围
	while (start < end)
	{
		int maxi = start, mini = start;
		for (j = start + 1;j <= end;j++)//每进行一次内部循环，同时找出数组的两个最值
		{
			if (arr[mini] > arr[j])
			{
				mini = j;
			}
			if (arr[maxi] < arr[j])
			{
				maxi = j;
			}
		}
		/*swap(&arr[mini], &arr[start]);//-》直接进行两次交换会出现bug，因此先交换mini与start指向的数组之中的值，
		swap(&arr[maxi], &arr[end]);*/  //但之后交换maxi时，maxi的值可能仍是start，但经过上一步交换，
										//start指向的已经变成了数组最小值，如此，导致bug

		//改进方法：交换前判断maxi是否等于start
		swap(&arr[mini], &arr[start]);
		if (start != maxi)
		{
			swap(&arr[maxi], &arr[end]);//若不等，则直接交换
		}
		else {
			swap(&arr[mini], &arr[end]);//若相等，则交换end与mini（经过上一步交换后，start指向的值已经换到了mini指向的位置）
		}
		start++;
		end--;
	}
}

int main()
{
	int arr[] = { 9,1,2,5,7,4,6,3,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	​​SelectionSort(arr, sz);
	int i = 0;
	for (i = 0;i < sz;i++)
	{
		printf("%d ", arr[i]);//1 2 3 4 5 6 7 8 9
	}
	printf("\n");
	return 0;
}
